11161. Фруктовый праздник

Корова Бесси забралась на кухню Фермера Джона и обнаружила там множество лимонов и апельсинов (неограниченное количество обоих видов фруктов) и хочет съесть как можно больше.

Максимальное значение сытости Бесси равно t. Поедание апельсина увеличивает ее сытость на a, а поедание лимона увеличивает ее сытость на b. Дополнительно, если она пожелает, Бесси может попить воды не более одного раза, что мгновенно уменьшит ее сытость вдвое (с округлением вниз).

Помогите определить максимальную сытость, которую сможет достичь Бесси.

Вход. Одна строка содержит три целых числа t (1 ≤ t ≤ 5 ⋅ 10⁶), a и b (1 ≤ a, b ≤ t).

Выход. Выведите одно целое число, представляющее максимальную сытость, которую сможет достичь Бесси.

Пример входа	Пример выхода
8 5 6	8

РЕШЕНИЕ

рюкзак

Анализ алгоритма

Имеется рюкзак вместимостью t. Доступны две вещи со стоимостями a и b. Каждую из них можно класть в рюкзак произвольное количество раз. Решаем задачу о рюкзаке для двух вещей.

Пусть dp[i] = 1, если Бесси может получить сытость, равную i. Теперь Бесси пьет воду. А именно для каждого значения i, для которого dp[i] = 1, установим dp[i / 2] = 1.

Теперь снова решаем задачу о рюкзаке для двух вещей. Находим сытости, которые сможет достичь Бесси после того, как выпила воды.

Пример

Рассмотрим приведенный пример. Решаем задачу рюкзака для апельсинов и лимонов.

Бесси пьет воду.

Снова решаем задачу рюкзака для апельсинов и лимонов.

Максимальная сытость Бесси равна 8.

Реализация алгоритма

Объявим массив dp, в котором dp[i] = 1, если Бесси может получить сытость, равную i.

#define MAX 5000001

int dp[MAX];

Читаем входные данные.

scanf("%d %d %d", &t, &a, &b);

Инициализируем рюкзак: сытость 0 можно достичь, если ничего не есть.

dp[0] = 1;

В рюкзак кладем апельсины.

for (i = a; i <= t; i++)

if (dp[i - a] == 1) dp[i] = 1;

В рюкзак кладем лимоны.

for (i = b; i <= t; i++)

if (dp[i - b] == 1) dp[i] = 1;

Бесси пьет воду. Если сытость i достигнута, то сытость i / 2 также может быть достигнута.

for (i = 1; i <= t; i++)

if (dp[i] == 1) dp[i / 2] = 1;

Снова решаем задачу рюкзака для апельсинов и лимонов.

for (i = a; i <= t; i++)

if (dp[i - a] == 1) dp[i] = 1;

for (i = b; i <= t; i++)

if (dp[i - b] == 1) dp[i] = 1;

Находим и выводим максимальную сытость, которую может достичь Бесси.

for (i = t; i > 0; i--)

if (dp[i] == 1) break;

printf("%d\n", i);

Python реализация

Читаем входные данные.

t, a, b = map(int, input().split())

Объявим массив dp, в котором dp[i] = 1, если Бесси может получить сытость, равную i.

dp = [0] * (t + 1)

Инициализируем рюкзак: сытость 0 можно достичь, если ничего не есть.

dp[0] = 1

В рюкзак кладем апельсины.

for i in range(a, t + 1):

if dp[i - a] == 1: dp[i] = 1

В рюкзак кладем лимоны.

for i in range(b, t + 1):

if dp[i - b] == 1: dp[i] = 1

Бесси пьет воду. Если сытость i достигнута, то сытость i / 2 также может быть достигнута.

for i in range(1, t + 1):

if dp[i] == 1: dp[i // 2] = 1

Снова решаем задачу рюкзака для апельсинов и лимонов.

for i in range(a, t + 1):

if dp[i - a] == 1: dp[i] = 1

for i in range(b, t + 1):

if dp[i - b] == 1: dp[i] = 1

Находим и выводим максимальную сытость, которую может достичь Бесси.

for i in range(t, 0, -1):

if dp[i] == 1: break

print(i)